package com.isaiah.graph.adjacencylist;


import java.util.LinkedList;

/**
 * @Title: 基于邻接表的有向图实现
 * @Description: ${todo}
 * @author: Haijun
 * @emial: isaiah@sohu.com
 * @date 2020/6/613:13
 */
public class Digraph {
    /** 顶点的数量 */
    private final int V;
    /** 边的数量 */
    private int E;
    /** 邻接表 */
    private LinkedList<Integer>[] adj;

    public Digraph(int v) {
        // 初始化顶点数量
        this.V = v;
        // 初始化边的数量
        this.E = 0;
        // 初始化邻接表
        this.adj = new LinkedList[v];
    }

    /**
     * 获取顶点数目
     * @return
     */
    public int V(){
        return V;
    }

    /**
     * 获取边的数目
     * @return
     */
    public int E(){
        return E;
    }

    /**
     * 向有向图中添加一条边<v, w>
     * @param v
     * @param w
     */
    public void addEdge(int v, int w){
        adj[v].addFirst(w);
        E++;
    }

    /**
     * 获取由v指出的边所连接的所有顶点
     * @param v
     * @return
     */
    public LinkedList<Integer> adj(int v){
        return adj[v];
    }

    /**
     * 该图的反向图
     * @return
     */
    public Digraph reverse(){
        // 创建有向图
        Digraph r = new Digraph(V);
        for (int v = 0; v < V;  v++){
            // 获取由该顶点v指出的所有边
            for (Integer w : adj[v]){
                // 原图中表示的是顶点v的边<v, w>,变成<w, v>
                r.addEdge(w, v);
            }
        }
        return r;
    }
}
